package cn.michael.dev.sort;

import java.util.Arrays;

/**
 * Created by hufenggang on 2021/10/21.
 *
 * 插入排序算法
 */
public class InsertionSort {

    /**
     *
     * @param nums
     */
    public static void insertionSort(int[] nums) {
        insertionSort(nums, 0, nums.length - 1);
    }

    /**
     * 对数组 nums 的子区间 [left, right] 使用插入排序
     *
     * @param nums 给定数组
     * @param left 左边界
     * @param right 右边界
     */
    public static void insertionSort(int[] nums, int left, int right) {
        // 特殊判断
        if (nums == null || nums.length <= 1) {
            return;
        }

        for (int i = left; i <= right; i++) {
            int temp = nums[i];
            int j = i;

            while (j > left && nums[j - 1] > temp) {
                nums[j] = nums[j - 1];
                j--;
            }
            nums[j] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{9, 4, 6, 8, 3, 10, 4, 6};
        insertionSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}
